\begin{abstract}
\begin{small}
%\small\baselineskip=9pt
We study how to spread $k$ tokens of information to every node on an
$n$-node dynamic network, the edges of which are changing at each
round. This basic {\em gossip problem} can be completed in $O(n +
k)$ rounds in any static network, and determining its complexity in
dynamic networks is central to understanding the algorithmic limits
and capabilities of various dynamic network models. Our focus is on
token-forwarding algorithms, which do not manipulate tokens in any way
other than storing, copying and forwarding them.

\vspace{0.1cm}

We first consider the {\em strongly adaptive} adversary model where in
each round, each node first chooses a token to broadcast to all its
neighbors (without knowing who they are), and then an adversary
chooses an arbitrary connected communication network for that round
with the knowledge of the tokens chosen by each node. We show that
$\Omega(nk/\log n + n)$ rounds are needed for any randomized
(centralized or distributed) token-forwarding algorithm to disseminate
the $k$ tokens, thus resolving an open problem raised
in~\cite{kuhn+lo:dynamic}. The bound applies to a wide class of
initial token distributions, including those in which each token is
held by exactly one node and {\em well-mixed} ones in which each node
has each token independently with a constant probability.

\vspace{0.1cm}

Our result for the strongly adaptive adversary model motivates us to
study the {\em weakly adaptive} adversary model where in each round,
the adversary is required to lay down the network first, and then each
node sends a possibly distinct token to each of its neighbors. We
propose a simple randomized distributed algorithm where in each round,
along every edge $(u,v)$, a token sampled uniformly at random from the
symmetric difference of the sets of tokens held by node $u$ and node
$v$ is exchanged. We prove that starting from any well-mixed
distribution of tokens where each node has each token independently
with a constant probability, this algorithm solves the $k$-gossip
problem in $O((n+k)\log n \log k)$ rounds with high probability over
the initial token distribution and the randomness of the protocol. We
then show how the above uniform sampling problem can be solved using
$\tilde O(\log n)$ bits of communication, making the overall algorithm
communication-efficient.

\vspace{0.1cm}

We next present a centralized algorithm that solves the gossip problem
for every initial distribution in $O((n + k)\log^2 n)$ rounds in the
offline setting where the entire sequence of communication networks is
known to the algorithm in advance. Finally, we present an $O(n
\min\{k, \sqrt{k \log n}\})$-round centralized offline algorithm in
which each node can only broadcast a single token to all of its
neighbors in each round.
\end{small}
\end{abstract}
